package randomthoughts.dp;

import java.util.HashSet;
import java.util.List;

/**LeetCode139
 * @author tongchen
 * @create 2023-04-18 20:00
 */
public class WordsSplit {
    public static void main(String[] args) {

    }
    //动规五部曲：1.dp[i]代表 s的前i个字符都相匹配 i代表当前下标 2.递推公式：dp[i]=contains(i,j)&&valid[j]3.初始化dp[0]=true(空字符串)4.从前到后遍历

    public static boolean isSplit(String s, List<String>strs){
        //创建set
        HashSet<String>set=new HashSet<>(strs);
        //创建dp
        boolean[]dp=new boolean[s.length()+1];
        //空字符串
        dp[0]=true;
        //题目要求的是按照字符序列进行排序然后进行判断，对于这种排序要求，我们选择先排容量，再排物品
        for(int i=1;i<=s.length();++i){
            for(int j=0;j<i&&dp[i]==false;++j){
                dp[i]=set.contains(s.substring(j, i))&&dp[j];
            }
        }
        return dp[s.length()];
    }
}
